//? 超时
function findMaximumXOR(nums: number[]): number {
    let max: number = Math.max(...nums)
    let n: number = 1
    while(max / n >= 2){
        n *= 2
    }
    //?  大于n的数组
    let maxI: number[] = nums.filter(x => x >= n)
    let out: number = 0
    //? 数组每个值与maxI每个值进行异或
    for(let i of nums){
        for(let j of maxI){
            out = Math.max(out,j ^ i)
        }
    }
    return out
};

function findMaximumXOR2(nums: number[]): number {
    const HIGH_BIT = 30;
    let x = 0;
    for (let k = HIGH_BIT; k >= 0; --k) {
        const seen = new Set();
        //? 将所有的 pre^k(a_j) 放入哈希表中
        for (const num of nums) {
            //? 如果只想保留从最高位开始到第 k 个二进制位为止的部分
            //? 只需将其右移 k 位
            seen.add(num >> k);
        }

        //? 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
        //? 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
        const xNext = x * 2 + 1;
        let found = false;

        //? 枚举 i
        for (const num of nums) {
            if (seen.has(xNext ^ (num >> k))) {
                found = true;
                break;
            }
        }

        if (found) {
            x = xNext;
        } else {
            //? 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
            //? 即为 x = x*2
            x = xNext - 1;
        }
    }
    return x;
};
//? 字典树解法 js版
// class TrieNode{
//     constructor(val, left, right){
//         this.val = val ? val : undefined;
//         this.left = left ? left : null;  //表示0节点
//         this.right = right ? right : null;    //表示1节点
//     }
// }
//
// const findMaximumXOR3 = (nums) => {
//     let trieRoot = new TrieNode(), HIGH_BIT = 30;
//
//     const add = (num) => {
//         let node = trieRoot;
//
//         for(let k = HIGH_BIT; k >= 0; k--){
//             let bit = (num >> k) & 1;
//
//             if(bit == 0){
//                 if(!node.left) node.left = new TrieNode();
//                 node = node.left;
//             }else{
//                 if(!node.right) node.right = new TrieNode();
//                 node = node.right;
//             }
//         }
//     };
//
//     const check = (num) => {
//         let node = trieRoot, x = 0;
//
//         for(let k = HIGH_BIT; k >= 0; k--){
//             let bit = (num >> k) & 1;
//
//             if(bit == 0){
//                 if(node.right){
//                     node = node.right;
//                     x = x * 2 + 1;
//                 }else{
//                     node = node.left;
//                     x = x * 2;
//                 }
//             }else{
//                 if(node.left){
//                     node = node.left;
//                     x = x * 2 + 1;
//                 }else{
//                     node = node.right;
//                     x = x * 2;
//                 }
//             }
//         }
//
//         return x;
//     };
//
//     let x = 0;
//
//     for(let i = 1; i < nums.length; i++){
//         add(nums[i - 1]);
//
//         x = Math.max(x, check(nums[i]));
//     }
//
//     return x;
// };
